Routines (alphabetical) > Routines: C > CONSTRAINED_MIN

CONSTRAINED_MIN

Syntax | Arguments | Keywords | Example | Version History

The CONSTRAINED_MIN procedure solves nonlinear optimization problems of the following form:

Minimize or maximize gp(X), subject to:

glb_i ≤ g_i(X) ≤ gub_i for i = 0,...,nfuns-1, i ≠ p

xlb_j ≤ x_j ≤ xub_j for j = 0,...,nvars-1

X is a vector of nvars variables, x₀ ,...,x_nvars-1, and G is a vector of nfuns functions g₀,...,g_nfuns-1, which all depend on X. Any of these functions may be nonlinear. Any of the bounds may be infinite and any of the constraints may be absent. If there are no constraints, the problem is solved as an unconstrained optimization problem. The program solves problems of this form by the Generalized Reduced Gradient Method. See References 1-4.

CONSTRAINED_MIN uses first partial derivatives of each function g_i with respect to each variable x_j. These are automatically computed by finite difference approximation (either forward or central differences).

CONSTRAINED_MIN is based on an implementation of the GRG algorithm supplied by Windward Technologies, Inc. See Reference 11.

Syntax

CONSTRAINED_MIN, X, Xbnd, Gbnd, Nobj, Gcomp, Inform [, EPSTOP =value] [, LIMSER=value] [, /MAXIMIZE] [, NSTOP =value] [, REPORT =filename] [, TITLE =string]

Arguments

X

An nvars-element vector. On input, X contains initial values for the variables. On output, X contains final values of the variable settings determined by CONSTRAINED_MIN.

Xbnd

Bounds on variables. Xbnd is an nvars x 2 element array.

Xbnd[j,0] is the lower bound for variable x[j].
Xbnd[j,1] is the upper bound for variable x[j].
Use -1.0e30 to denote no lower bound and 1.0e30 for no upper bound.

Gbnd

Bounds on constraint functions. Gbnd is an nfuns x 2 element array.

Gbnd[i,0] is the lower bound for function g[i].
Gbnd[i,1] is the upper bound for function g[i].
use -1.0e30 to denote no lower bound and 1.0e30 for no upper bound.

Bounds on the objective function are ignored; set them to 0.

Nobj

Index of the objective function.

Gcomp

A scalar string specifying the name of a user-supplied IDL function. This function must accept an nvars-element vector argument x of variable values and return an nfuns-element vector G of function values.

Inform

Termination status returned from CONSTRAINED_MIN.

Inform Argument Values
Inform value	Message
0	Kuhn-Tucker conditions satisfied. This is the best possible indicator that an optimal point has been found.
1	Fractional change in objective less than EPSTOP for NSTOP consecutive iterations. See Keywords below. This is not as good as Inform=0, but still indicates the likelihood that an optimal point has been found.
2	All remedies have failed to find a better point. User should check functions and bounds for consistency and, perhaps, try other starting values.
3	Number of completed 1-dimensional searches exceeded LIMSER. See Keywords below. User should check functions and bounds for consistency and, perhaps, try other starting values. It might help to increase LIMSER. Use LIMSER=larger_value to do this.
4	Objective function is unbounded. CONSTRAINED_MIN has observed dramatic change in the objective function over several steps. This is a good indication that the objective function is unbounded. If this is not the case, the user should check functions and bounds for consistency.
5	Feasible point not found. CONSTRAINED_MIN was not able to find a feasible point. If the problem is believed to be feasible, the user should check functions and bounds for consistency and perhaps try other starting values.
6	Degeneracy has been encountered. The point returned may be close to optimal. The user should check functions and bounds for consistency and perhaps try other starting values.
7	Noisy and nonsmooth function values. Possible singularity or error in the function evaluations.
8	Optimization process terminated by user request.
9	Maximum number of function evaluations exceeded.
–1	Fatal Error. Some condition, such as nvars < 0, was encountered. CONSTRAINED_MIN documented the condition in the report and terminated. In this case, the user needs to correct the input and rerun CONSTRAINED_MIN.
–2	Fatal Error. The report file could not be opened. Check the filename specified via the REPORT keyword, and make sure you have write privileges to the specified path.
–3	Fatal Error. Same as Inform = –1. In this case, the REPORT keyword was not specified. Specify the REPORT keyword and rerun CONSTRAINED_MIN, then check the report file for more detail on the error.

Keywords

EPSTOP

Set this keyword to specify the CONSTRAINED_MIN convergence criteria. If the fractional change in the objective function is less than EPSTOP for NSTOP consecutive iterations, the program will accept the current point as optimal. CONSTRAINED_MIN will accept the current point as optimal if the Kuhn-Tucker optimality conditions are satisfied to EPSTOP. By default, EPSTOP = 1.0e-4.

LIMSER

If the number of completed one dimensional searches exceeds LIMSER, CONSTRAINED_MIN terminates and returns inform = 3. By default: LIMSER = 10000.

MAXIMIZE

By default, the CONSTRAINED_MIN procedure performs a minimization. Set the MAXIMIZE keyword to perform a maximization instead.

NSTOP

REPORT

Set this keyword to specify a name for the CONSTRAINED_MIN report file. If the specified file does not exist, it will be created. Note that if the file cannot be created, no error message will be generated. If the specified file already exists, it will be overwritten. By default, CONSTRAINED_MIN does not create a report file.

TITLE

Set this keyword to specify a title for the problem in the CONSTRAINED_MIN report.

Example

This example has 5 variables {X0, X1, ..., X4}, bounded above and below, a quadratic objective function {G3}, and three quadratic constraints {G0, G1, G2}, with both upper and lower bounds. See the Himmelblau text [7], problem 11.

Minimize:

G3 = 5.3578547X2X2 + 0.8356891X0X4 + 37.293239X0 - 40792.141

Subject to:

0 < G0 = 85.334407 + 0.0056858X1X4 + 0.0006262X0X3 - 0.0022053X2X4 < 92

90 < G1 = 80.51249 + 0.0071317X1X4 + 0.0029955X0X1 + 0.0021813X2X2 <110

20 < G2 = 9.300961 + 0.0047026X2X4 + 0.0012547X0X2 + 0.0019085X2X3 < 25

and,

78 < X0 < 102

33 < X1 < 45

27 < X2 < 45

27 < X3 < 45

27 < X4 < 45

This problem is solved starting from X = {78, 33, 27, 27, 27} which is infeasible because constraint G2 is not satisfied at this point.

The constraint functions and objective function are evaluated by HMBL11:

; Himmelblau Problem 11

; 5 variables and 4 functions

FUNCTION HMBL11, x

g = DBLARR(4)

g[0] = 85.334407 + 0.0056858*x[1]*x[4] + 0.0006262*x[0] $

*x[3] - 0.0022053*x[2]*x[4]

g[1] = 80.51249 + 0.0071317*x[1]*x[4] + 0.0029955*x[0] $

*x[1] + 0.0021813*x[2]*x[2]

g[2] = 9.300961 + 0.0047026*x[2]*x[4] + 0.0012547*x[0]* $

x[2] + 0.0019085*x[2]*x[3]

g[3] = 5.3578547*x[2]*x[2] + 0.8356891*x[0]*x[4] $

+ 37.293239*x[0] - 40792.141

RETURN, g

END

; Example problem for CONSTRAINED_MIN

; Himmelblau Problem 11

; 5 variables and 3 constraints

; Constraints and objective defined in HMBL11

xbnd = [[78, 33, 27, 27, 27], [102, 45, 45, 45, 45]]

gbnd = [[0, 90, 20, 0], [92, 110, 25, 0 ]]

nobj = 3

gcomp = 'HMBL11'

title = 'IDL: Himmelblau 11'

report = 'hmbl11.txt'

x = [78, 33, 27, 27, 27]

CONSTRAINED_MIN, x, xbnd, gbnd, nobj, gcomp, inform, $

REPORT = report, TITLE = title

g = HMBL11(x)

; Print minimized objective function for HMBL11 problem:

PRINT, g[nobj]

References

1. Lasdon, L.S., Waren, A.D., Jain, A., and Ratner, M., “Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming”, ACM Transactions on Mathematical Software, Vol. 4, No. 1, March 1978, pp. 34-50.

2. Lasdon, L.S. and Waren, A.D., “Generalized Reduced Gradient Software for Linearly and Nonlinearly Constrained Problems”, in “Design and Implementation of Optimization Software”, H. Greenberg, ed., Sijthoff and Noordhoff, pubs, 1979.

3. Abadie, J. and Carpentier, J. “Generalization of the Wolfe Reduced Gradient Method to the Case of Nonlinear Constraints”, in Optimization, R. Fletcher (ed.), Academic Press London; 1969, pp. 37-47.

4. Murtagh, B.A. and Saunders, M.A. “Large-scale Linearly Constrained Optimization”, Mathematical Programming, Vol. 14, No. 1, January 1978, pp. 41-72.

5. Powell, M.J.D., “Restart Procedures for the Conjugate Gradient Method,” Mathematical Programming, Vol. 12, No. 2, April 1977, pp. 241-255.

6. Colville, A.R., “A Comparative Study of Nonlinear Programming Codes,” I.B.M. T.R. no. 320-2949 (1968).

7. Himmelblau, D.M., Applied Nonlinear Programming, McGraw-Hill Book Co., New York, 1972.

8. Fletcher, R., “A New Approach to Variable Metric Algorithms”, Computer Journal, Vol. 13, 1970, pp. 317-322.

9. Smith, S. and Lasdon, L.S., Solving Large Sparse Nonlinear Programs Using GRG, ORSA Journal on Computing, Vol. 4, No. 1,Winter 1992, pp. 1-15.

10. Luenbuerger, David G., Linear and Nonlinear Programming, Second Edition, Addison-Wesley, Reading Massachusetts, 1984.

11. Windward Technologies, GRG2 Users’s Guide, 1997.

Version History

5.1	Introduced